package Tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class leet_102 {

}

class Solution_102 {
    /**
     * 层序遍历 BFS算法
     * 利用队列，第一次将首节点加入，每次循环当前节点的大小的结点，这里是为了更好的展示出层级的概念
     * 循环过程首先将队首元素抛出，在将左右结点如果存在就加入队列，由于之前的结点先加入，所以不会造成
     * 紊乱，最后如果队列为空代表已经遍历玩整个树节点了。
     * 本题中每一个层级的区分很关键！！ 就是要在while 循环 内部使用for循环首先敲定这个层级的大小在做
     * 循环。
     * @param root 树的根节点
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        // 设置一个队列
        Queue<TreeNode> queue = new LinkedList<>();
        if(root!=null){
            // 如果首节点不为空就直接放入队列
            queue.offer(root);
        }
        // 结果节点
        List<List<Integer>> result = new ArrayList<>();
        while(!queue.isEmpty()){
            // 只要队列不为空就可以走
            // 存储每一个层级的队列
            List<Integer> tmpList = new ArrayList<>();
            // 千万不要用动态的，用静态的，保证每次循环结束都是一个层级的
            int size = queue.size();
            for(int i=0; i<size; i++){
                // 弹出树节点
                TreeNode node = queue.poll();
                tmpList.add(node.val);
                // 将左右结点加入队列中
                if(node.left!=null) {
                    queue.offer(node.left);
                }
                if(node.right!=null){
                    queue.offer(node.right);
                }
            }
            result.add(tmpList);
        }
        return result;
    }

}

